package zuosheng.string;

/**
 * @author lj
 * @Description: KMP
 * @date 2020-11-16 17:28
 * @QQ 851477108
 */


public class KMP {
    public static void main(String[] args) {
        String str = "abcabcababaccc";
        String match = "ababa";
        System.out.println(getIndexOf(str, match));

    }
    //利用kmp算法获得m字符串在s字符串中开始的位置
    public static int getIndexOf(String str1, String str2) {
        if (str1 == null || str2 == null || str2.length() < 1 || str1.length() < str2.length()) {
            return -1;
        }
        char[] chars1 = str1.toCharArray();
        char[] chars2 = str2.toCharArray();
        //str1下标和str2下标
        int i = 0;
        int j = 0;
        //获得next数组,表示最长前缀（不包括最后一个元素）跟最长后缀（不包括第一个元素）是否存在相等的情况
        int[] next = getNextArray(chars2);
        while (i < chars1.length && j < chars2.length) {
            //如果两者相等，则直接往下比较
            if (chars1[i] == chars2[j]) {
                i++;
                j++;
            } else if (next[j] == -1) {
                //如果两者不相等，并且str2的第一个字符就不相等，str1直接往下
                i++;
            } else {
                //如果两者不相等，并且str1与str2有字符相等，m滑到next[mi]位置
                j = next[j];
            }
        }
        //chars2足够str2长度，说明str1中存在str2，返回起始位置，否则返回-1
        return j == chars2.length ? i - j : -1;
    }

    //利用归纳法获得next数组，next数组的值为[-1,0,...,k],0为不存在，k为最大前缀==最大后缀中，前缀串的后一个字符下标
    public static int[] getNextArray(char[] str2) {
        if (str2.length == 1) {
            return new int[] { -1 };
        }
        int[] next = new int[str2.length];
        next[0] = -1;
        next[1] = 0;
        //pos为当前str2的位置，起始是第三个数
        int pos = 2;
        //cn为最大前缀==最大后缀中，前缀串的后一个字符下标
        int cn = 0;
        while (pos < next.length) {
            //str2当前值的前一个字符等于前缀串的后一个字符
            if (str2[pos - 1] == str2[cn]) {
                next[pos++] = ++cn;
            } else if (cn > 0) {
                //不相等一直找前一个next
                cn = next[cn];
            } else {
                //不存在前缀串==后缀串
                next[pos++] = 0;
            }
        }
        return next;
    }


}
